//返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。 
//
// (回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right
// 的任何后代，值总 > node.val。此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。） 
//
// 题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。 
//
// 
//
// 示例： 
//
// 输入：[8,5,1,7,10,12]
//输出：[8,5,10,1,7,null,12]
//
// 
//
// 
//
// 提示： 
//
// 
// 1 <= preorder.length <= 100 
// 1 <= preorder[i] <= 10^8 
// preorder 中的值互不相同 
// 
// Related Topics 栈 树 二叉搜索树 数组 二叉树 单调栈 
// 👍 159 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * Java：前序遍历构造二叉搜索树
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P1008_ConstructBinarySearchTreeFromPreorderTraversal {
    public static void main(String[] args) {
        Solution solution = new P1008_ConstructBinarySearchTreeFromPreorderTraversal().new Solution();
        // TODO 此处开始你的表演
        int[] arr = MyUtil.createArray(8, 5, 1, 7, 10, 12);
        solution.bstFromPreorder(arr);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public TreeNode bstFromPreorder(int[] preorder) {
            if (preorder == null || preorder.length == 0) {
                return null;
            }
            return process(preorder, 0, preorder.length - 1);

        }

        /**
         * 当前头结点 left，在left到right之间建一棵树
         */
        public TreeNode process(int[] arr, int left, int right) {
            if (left > right) {
                return null;
            }
            // 找到右边最近的比index大的数
            int index = left;
            for (; index <= right; index++) {
                if (arr[index] > arr[left]) {
                    break;
                }
            }

            // 头节点
            TreeNode head = new TreeNode(arr[left]);
            head.left = process(arr, left + 1, index - 1);
            head.right = process(arr, index, right);
            return head;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}